/****************************************************
File Name:  quickSortFileMiddle.cpp
Author:     Animesh Sharma
Date:       11/2005
Description:    Source code for Quicksort Algorithm - 
                String Pointer Array based Implementation(Project 3 cs352)
Submission Date: 1st Dec 2005
Project Due Date: 1st Dec 2005
****************************************************/


#include <iostream>
#include <fstream>


using namespace std;

void QuickSort (char** wordList, int indexLow, int indexHigh);
int Partition (char** wordList, int indexLow, int indexHigh);
int compVal=0;


int main ()
{
	char inputFile[512], outputFile[512];
	printf ("Enter the Input File: ");
	gets (inputFile);
	printf ("Enter the Name of Output File: ");
	gets (outputFile);

	const int arraySizeIncrease = 1000000;
	int arraySize = arraySizeIncrease, wordCount = 0;
	char** wordListArray = new char* [arraySize];
	char wordSize [512];
	ifstream fileInputStream(inputFile);
	while (fileInputStream >> wordSize )
	{
		wordListArray[wordCount] = new char [strlen (wordSize) + 1];
		strcpy (wordListArray[wordCount], wordSize);
		wordCount++;
		//If the File has more then 1000000 Words!
		if (wordCount % arraySizeIncrease == 0)
		{
			char** oldSize = wordListArray;
			arraySize += arraySizeIncrease;
			wordListArray = new char* [arraySize];
			memcpy (wordListArray, oldSize, wordCount * sizeof(char*));
			delete oldSize;
		}
	}
	fileInputStream.close();

	int start = clock();

//	Sort the word list array
	QuickSort (wordListArray, 0, wordCount - 1);
//	InsertionSort(wordListArray, wordCount);

	int stop = clock();
	
//	Report the elapsed time

	cout << "Elapsed time = " << stop - start << " ticks" << endl;

	FILE* fileOutputStream = fopen (outputFile, "wt");
	for (int cntIndex = 0; cntIndex < wordCount; cntIndex++)
	{
		fprintf (fileOutputStream, "%s\n", wordListArray[cntIndex]);
	}
	fclose (fileOutputStream);

	for (int cntIndexN = 0; cntIndexN < wordCount; cntIndexN++)
	{
		delete wordListArray[cntIndexN];
	}
	delete wordListArray;
	wordListArray = NULL;

	cout << "\nOutput file Written.\n\n";
	cout << "Number of comparisions\t" <<     compVal << "\n";
	
	getchar();
	return 0;
}

void QuickSort (char** wordList, int indexLow, int indexHigh)
{
	if (indexLow < indexHigh)
	{
		int splitIndex = Partition (wordList, indexLow, indexHigh);
		QuickSort (wordList, indexLow, splitIndex - 1);
		QuickSort (wordList, splitIndex + 1, indexHigh);
	}
}

int Partition (char** wordList, int indexLow, int indexHigh)
{
	int indexLeft = indexLow + 1;
	int indexRight = indexHigh;
    char* indexPivot = wordList[(indexHigh+indexLow)/2];;

	char* indexSwap;
	while (indexLeft <= indexRight)
	{
		while (indexLeft <= indexRight && strcmp (wordList[indexLeft], indexPivot) <= 0)
		{
			indexLeft = indexLeft + 1;
            compVal++;
        }
		while (indexLeft <= indexRight && strcmp (wordList[indexRight], indexPivot) > 0)
        {
			indexRight = indexRight - 1;
            compVal++;
        }
		if (indexLeft < indexRight)
		{
			indexSwap = wordList[indexLeft];
			wordList[indexLeft] = wordList[indexRight];
			wordList[indexRight] = indexSwap;
			indexLeft = indexLeft + 1;
			indexRight = indexRight - 1;
            compVal++;
		}
	}
	indexSwap = wordList[indexLow];
	wordList[indexLow] = wordList[indexRight];
	wordList[indexRight] = indexSwap;
	return indexRight;
}


